package com.example.jianzhioffer;

import java.util.ArrayList;
import java.util.Collections;

/**
 * Created by Quincy on 2018/9/23.
 * 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 * 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
 */
public class Permutation {

    /**
     * 把字符串分成两部分，一部分是第一个字符，另一个部分是后面其余的字符串
     * 拿第一个字符和后面的字符串依次交换，这是一个递归的过程
     * 注意：在递归里第一次交换是自身和自身的交换，保证不缺少字符串
     * */

    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if (str == null || str.length() == 0)
            return list;
        char[] strArr = str.toCharArray();
        permu(list, strArr, 0);
        Collections.sort(list);
        return list;
    }

    private void permu(ArrayList<String> list, char[] strArr, int start) {
        if (start == strArr.length - 1){
            String result = String.valueOf(strArr);
            if (list.indexOf(result) < 0)
                list.add(String.valueOf(strArr));
        }
        for (int i = start; i < strArr.length; i++){
            char temp = strArr[i];
            strArr[i] = strArr[start];
            strArr[start] = temp;
            permu(list, strArr, start + 1);
            temp = strArr[i];
            strArr[i] = strArr[start];
            strArr[start] = temp;
        }
        return;
    }
}
